#include "graph.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Graph createGraph()
{
	Graph graph = (Graph)malloc(sizeof(MGraph));
	graph->vertexNum = graph->edgeNum = 0;
	return graph;
}

int locateVex(Graph graph, char v)
{
	int i;
	for (i = 0; i < graph->vertexNum; i++)
	{
		if (graph->vertexs[i] == v)
		{
			return i;
		}
	}
	return -1;
}

int firstAdjVex(Graph graph, int v)
{
	int i;
	for (i = 0; i < graph->vertexNum; i++)
	{
		if (graph->edges[v][i] != INFINITE)
		{
			return i;
		}
	}
	return -1;
}

int nextAdjVex(Graph graph, int v, int w)
{
	int i;
	for (i = w + 1; i < graph->vertexNum; i++)
	{
		if (graph->edges[v][i] != INFINITE)
		{
			return i;
		}
	}
	return -1;
}

void insertVex(Graph graph, char v)
{
	graph->vertexs[graph->vertexNum++] = v;
	// 把邻接矩阵新增一行一列并初始化
	int i;
	for (i = 0; i < graph->vertexNum; i++)
	{
		// 增一行
		graph->edges[graph->vertexNum - 1][i] = i == graph->vertexNum - 1 ? 0 : INFINITE;
		// 增一列
		graph->edges[i][graph->vertexNum - 1] = i == graph->vertexNum - 1 ? 0 : INFINITE;
	}
}

void insertVexs(Graph graph, char vexs[])
{
	int i, n = strlen(vexs);
	for (i = 0; i < n; i++)
	{
		insertVex(graph, vexs[i]);
	}
}

void insertArc(Graph graph, int v, int w, int weight)
{
	graph->edges[v][w] = weight;
	graph->edgeNum++;
}

void insertArcs(Graph graph, int start[], int end[], int weights[], int n, int undirect)
{
	int i;
	for (i = 0; i < n; i++)
	{
		insertArc(graph, start[i], end[i], weights[i]);
		if (undirect)
		{
			insertArc(graph, end[i], start[i], weights[i]);
		}
	}
}

#ifndef CHECK_VISIT
#define CHECK_VISIT

/// @brief 检查辅助数组中是否还有没访问到的
/// @param visit 访问辅助数组
/// @param length 顶点个数
/// @return 若有没访问到的返回其下标，否则返回-1
int checkVisit(int visit[], int length)
{
	int i;
	for (i = 0; i < length; i++)
	{
		if (!visit[i])
		{
			return i;
		}
	}
	return -1;
}

#endif

void DFS(Graph graph, int start, int visit[])
{
	// 先访问当前点
	printf("%c ", graph->vertexs[start]);
	visit[start] = 1;
	// 遍历下标
	int i;
	// 寻找start的邻接点
	for (i = 0; i <= graph->vertexNum; i++)
	{
		// 如果说当前邻接点没有被访问过则进行递归访问
		if (graph->edges[start][i] != INFINITE && !visit[i])
		{
			DFS(graph, i, visit);
		}
	}
}

void DFSTraverse(Graph graph)
{
	// 遍历下标，辅助数组以及第一个没被访问到的点下标
	int i, visit[graph->vertexNum], notVisited;
	// 初始化辅助下标
	for (i = 0; i < graph->vertexNum; i++)
	{
		visit[i] = 0;
	}
	// 开始访问
	for (notVisited = checkVisit(visit, graph->vertexNum); notVisited != -1; notVisited = checkVisit(visit, graph->vertexNum))
	{
		DFS(graph, notVisited, visit);
	}
	printf("\n");
}

void BFSTraverse(Graph graph)
{
	// 遍历下标，辅助队列长度、第一个没被访问到的点下标、临时下标、对尾和队头指针
	int i, queueMax = 1000, notVisited, temp, rear = 0, front = 0;
	// 辅助循环队列、访问辅助数组
	int queue[queueMax], visit[graph->vertexNum];
	// 初始化辅助下标
	for (i = 0; i < graph->vertexNum; i++)
	{
		visit[i] = 0;
	}
	// 开始遍历
	for (notVisited = checkVisit(visit, graph->vertexNum); notVisited != -1; notVisited = checkVisit(visit, graph->vertexNum))
	{
		// 起始顶点入队并访问
		queue[rear] = notVisited;
		rear = (rear + 1) % queueMax;
		printf("%c ", graph->vertexs[notVisited]);
		visit[notVisited] = 1;
		while (rear != front)
		{
			// 出队
			temp = queue[front];
			front = (front + 1) % queueMax;
			// 依次访问出队元素的邻接点并将它们入队
			for (i = 0; i < graph->vertexNum; i++)
			{
				if (graph->edges[temp][i] != INFINITE && !visit[i])
				{
					// 入队并访问
					queue[rear] = i;
					rear = (rear + 1) % queueMax;
					printf("%c ", graph->vertexs[i]);
					visit[i] = 1;
				}
			}
		}
	}
	printf("\n");
}

void printGraph(Graph graph)
{
	printf("顶点：\n");
	int i, j, weight;
	for (i = 0; i < graph->vertexNum; i++)
	{
		printf("%c ", graph->vertexs[i]);
	}
	printf("\n");
	printf("邻接矩阵：\n");
	for (i = 0; i < graph->vertexNum; i++)
	{
		for (j = 0; j < graph->vertexNum; j++)
		{
			weight = graph->edges[i][j];
			if (weight == INFINITE)
			{
				printf("-  ");
				continue;
			}
			printf("%-2d ", weight);
		}
		printf("\n");
	}
}